
//743.网络延迟时间
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        //求最短路问题：Dijkstra 算法
        //先使用一个二维数组记录每个位置的距离,如果两个位置之间没有联系就设置为INT_MAX

        vector<vector<int>> path(n,vector<int>(n,INT_MAX/2));  //记录每个节点之间的距离
        for(auto& tmp : times)
        {
            int x = tmp[0]-1,y = tmp[1]-1,t = tmp[2];
            path[x][y]=t;
        }

        vector<int> vist(n);                    //记录k已经到过哪些位置了
        vector<int> need_t(n,INT_MAX);          //记录k到各个位置的最小之间
        need_t[k-1]=0;                          //将起始位置的距离置为0

        function<int()> GetNext=[&]()           //计算need_t数组中的最小值,作为下一个起始位置
        {
            int ret = -1, t = INT_MAX;
            for(int i = 0;i <n ;i++)
                if(!vist[i]&& t > need_t[i]) ret=i,t = need_t[i];
            return ret;
        };
        int point = GetNext(),clock=0;
        while(point != -1)
        {
            clock = need_t[point];              //当前时间
            vist[point] = 1;
            //从point位置开始向外进行扩展
            auto& nums = path[point];
            for(int k = 0;k < n;k++)
                need_t[k] = min(need_t[k],clock + path[point][k]);

            point = GetNext();
        }

        int ret = 0;
        for(int i = 0;i < n;i++)                //计算出扩展节点需要的最大时间
            ret = max(ret,need_t[i]);

        return ret>=INT_MAX/2?-1:ret;
    }
};